package com.kevinkk.tree;

/**
 * 给定一个二叉树，判断它是否是平衡二叉树
 *
 * 在递归获得一个二叉树的高度时，由于是后序遍历，因此可以轻松获得一个节点两个子树的高度
 * 如果一个子树不满足平衡二叉树的定义，则可以将这个子树的高度设置为无穷小
 * 如果所有的子树都是平衡二叉树，那么这个二叉树的高度将是非负的，反之不是
 */
public class BalancedBinaryTree {
    class Solution {
        public boolean isBalanced(TreeNode root) {
            return getDepth(root) >= 0;
        }

        private int getDepth(TreeNode node){
            if(node == null) return 0;
            int left = getDepth(node.left);
            int right = getDepth(node.right);

            if(left + right < 0) return Integer.MIN_VALUE;
            if(Math.abs(left-right) > 1) return Integer.MIN_VALUE;
            return Math.max(left, right) + 1;
        }
    }
}
